package com.yanceysong.codetop.s21_s30;

import com.yanceysong.common.ListNode;


public class S25_Mid_143_重排链表 {
    /**
     * LeetCode链接
     * <a href="https://leetcode.cn/problems/reorder-list/description/">...</a>
     * <p>
     * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     * L0 → L1 → … → Ln - 1 → Ln
     * 请将其重新排列后变为：
     * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
     * <p>
     * 示例 1：
     * 输入：head = [1,2,3,4]
     * 输出：[1,4,2,3]
     * <p>
     * 示例 2：
     * 输入：head = [1,2,3,4,5]
     * 输出：[1,5,2,4,3]
     * <p>
     * ==================== 重排链表算法图解 ====================
     * <p>
     * 算法思路：三步走
     * 1.找中点：使用快慢指针找到链表的中点，将链表一分为二。
     * 2.反转后半部分：将后半部分的链表进行反转。
     * 3.合并链表：将反转后的后半部分链表交错合并到前半部分链表中。
     * <p>
     * 执行示例：head = [1,2,3,4,5]
     * <p>
     * 第1步：找中点**
     * slow: 1 -> 2 -> 3
     * fast: 1 -> 3 -> 5
     * 中点为 `3`。链表被分为 `[1,2,3]` 和 `[4,5]`。
     * <p>
     * 第2步：反转后半部分**
     * 原始后半部分: 4 -> 5
     * 反转后:         5 -> 4
     * <p>
     * 第3步：合并链表**
     * 前半部分 (l1): 1 -> 2 -> 3
     * 后半部分 (l2): 5 -> 4
     * <p>
     * 合并过程：
     * 1. `1.next = 5`, `5.next = 2` -> `1 -> 5 -> 2 -> 3 -> 4`
     * 2. `2.next = 4`, `4.next = 3` -> `1 -> 5 -> 2 -> 4 -> 3`
     * 3. `l2` 变为空，合并结束。
     * <p>
     * 最终结果：1 -> 5 -> 2 -> 4 -> 3
     * <p>
     * ===============================================================
     */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        // 步骤1: 找中点，分割链表
        ListNode midNode = findMiddleNode(head);
        ListNode firstHalf = head;
        ListNode secondHalf = midNode.next;
        midNode.next = null; // 断开链表

        // 步骤2: 反转后半部分链表
        secondHalf = reverseList(secondHalf);

        // 步骤3: 合并两个链表
        mergeLists(firstHalf, secondHalf);
    }

    /**
     * 使用快慢指针找到链表的中点
     */
    public ListNode findMiddleNode(ListNode head) {
        ListNode slowPointer = head;
        ListNode fastPointer = head;
        while (fastPointer.next != null && fastPointer.next.next != null) {
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
        }
        return slowPointer;
    }

    /**
     * 反转链表
     */
    public ListNode reverseList(ListNode head) {
        ListNode prevNode = null;
        ListNode currentNode = head;
        while (currentNode != null) {
            ListNode nextNode = currentNode.next;
            currentNode.next = prevNode;
            prevNode = currentNode;
            currentNode = nextNode;
        }
        return prevNode;
    }

    /**
     * 交错合并两个链表
     */
    public void mergeLists(ListNode firstHalf, ListNode secondHalf) {
        while (firstHalf != null && secondHalf != null) {
            // 暂存 next 节点
            ListNode firstHalfNext = firstHalf.next;
            ListNode secondHalfNext = secondHalf.next;

            // 将 secondHalf 的头节点插入到 firstHalf 后面
            firstHalf.next = secondHalf;
            secondHalf.next = firstHalfNext;

            // 移动指针，准备下一轮合并
            firstHalf = firstHalfNext;
            secondHalf = secondHalfNext;
        }
    }

    public static void main(String[] args) {
        S25_Mid_143_重排链表 solution = new S25_Mid_143_重排链表();

        System.out.println("=== 重排链表测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同长度链表测试
        System.out.println("\n--- 测试3: 不同长度链表测试 ---");
        testDifferentLengths(solution);

        // 测试4: 特殊情况测试
        System.out.println("\n--- 测试4: 特殊情况测试 ---");
        testSpecialCases(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S25_Mid_143_重排链表 solution) {
        // 示例1: 偶数长度 [1,2,3,4] -> [1,4,2,3]
        int[] input1 = {1, 2, 3, 4};
        int[] expected1 = {1, 4, 2, 3};
        testReorderList(solution, input1, expected1, "题目示例1(偶数)");

        // 示例2: 奇数长度 [1,2,3,4,5] -> [1,5,2,4,3]
        int[] input2 = {1, 2, 3, 4, 5};
        int[] expected2 = {1, 5, 2, 4, 3};
        testReorderList(solution, input2, expected2, "题目示例2(奇数)");

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S25_Mid_143_重排链表 solution) {
        // 测试1: null输入
        solution.reorderList(null);
        System.out.println("null输入: null -> null (期望: null)");
        // 无需断言，不崩溃即可

        // 测试2: 单节点
        int[] input2 = {1};
        int[] expected2 = {1};
        testReorderList(solution, input2, expected2, "单节点");

        // 测试3: 两个节点
        int[] input3 = {1, 2};
        int[] expected3 = {1, 2};
        testReorderList(solution, input3, expected3, "两个节点");

        // 测试4: 三个节点
        int[] input4 = {1, 2, 3};
        int[] expected4 = {1, 3, 2};
        testReorderList(solution, input4, expected4, "三个节点");

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同长度的链表
     */
    private static void testDifferentLengths(S25_Mid_143_重排链表 solution) {
        // 测试1: 长度为6
        int[] input1 = {1, 2, 3, 4, 5, 6};
        int[] expected1 = {1, 6, 2, 5, 3, 4};
        testReorderList(solution, input1, expected1, "长度为6");

        // 测试2: 长度为7
        int[] input2 = {1, 2, 3, 4, 5, 6, 7};
        int[] expected2 = {1, 7, 2, 6, 3, 5, 4};
        testReorderList(solution, input2, expected2, "长度为7");

        System.out.println("✓ 不同长度链表测试通过");
    }

    /**
     * 测试特殊情况
     */
    private static void testSpecialCases(S25_Mid_143_重排链表 solution) {
        // 测试1: 包含负数
        int[] input1 = {-1, -2, -3, -4};
        int[] expected1 = {-1, -4, -2, -3};
        testReorderList(solution, input1, expected1, "包含负数");

        // 测试2: 包含零
        int[] input2 = {0, 1, 2, 3};
        int[] expected2 = {0, 3, 1, 2};
        testReorderList(solution, input2, expected2, "包含零");

        // 测试3: 相同元素
        int[] input3 = {1, 1, 1, 1};
        int[] expected3 = {1, 1, 1, 1};
        testReorderList(solution, input3, expected3, "相同元素");

        System.out.println("✓ 特殊情况测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S25_Mid_143_重排链表 solution) {
        // 测试1: 中等规模
        System.out.println("性能测试1: 100个节点");
        testPerformanceCase(solution, 100);

        // 测试2: 较大规模
        System.out.println("性能测试2: 500个节点");
        testPerformanceCase(solution, 500);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S25_Mid_143_重排链表 solution, int nodeCount) {
        ListNode head = createList(createRangeArray(1, nodeCount));
        long startTime = System.currentTimeMillis();
        solution.reorderList(head);
        long endTime = System.currentTimeMillis();

        assert head != null : "性能测试：结果不应为空";
        System.out.println("  节点数: " + nodeCount +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        assert (endTime - startTime) < 100 : "性能测试：执行时间过长";
    }

    /**
     * 创建链表的辅助方法
     */
    private static ListNode createList(int[] values) {
        if (values == null || values.length == 0) return null;
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int value : values) {
            current.next = new ListNode(value);
            current = current.next;
        }
        return dummy.next;
    }

    /**
     * 将链表转换为数组的辅助方法
     */
    private static int[] listToArray(ListNode head) {
        if (head == null) return new int[0];
        int size = 0;
        ListNode current = head;
        while (current != null) {
            size++;
            current = current.next;
        }
        int[] array = new int[size];
        current = head;
        for (int i = 0; i < size; i++) {
            array[i] = current.val;
            current = current.next;
        }
        return array;
    }

    /**
     * 打印数组的辅助方法
     */
    private static void printArray(int[] arr) {
        System.out.print(java.util.Arrays.toString(arr));
    }

    /**
     * 创建范围数组的辅助方法
     */
    private static int[] createRangeArray(int start, int end) {
        int[] array = new int[end - start + 1];
        for (int i = 0; i < array.length; i++) {
            array[i] = start + i;
        }
        return array;
    }

    /**
     * 测试重排链表的辅助方法
     */
    private static void testReorderList(S25_Mid_143_重排链表 solution, int[] inputArray, int[] expected, String description) {
        ListNode head = createList(inputArray);
        solution.reorderList(head);
        int[] actual = listToArray(head);

        System.out.print(description + " - 输入: ");
        printArray(inputArray);
        System.out.print(" -> 输出: ");
        printArray(actual);
        System.out.print(" (期望: ");
        printArray(expected);
        System.out.println(")");

        assert java.util.Arrays.equals(actual, expected) : description + "测试失败";
    }
}

